﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using LongestDesc.Question;
namespace LongestDesc.Answer
{
    class Libby : ILongestDesc
    {
        public int GetLongestDesc(int[] iarr)
        {
            if (iarr.Length == 0)
            {
                return 0;
            }
            else if (iarr.Length == 1)
            {
                return 1;
            }

            int count = 0;
            int[] storage = new int[iarr.Length];
            storage[0] = iarr[0];

            for (int i = 1; i < iarr.Length; i++)
            {
                if (iarr[i] > storage[0])
                {
                    storage[0] = iarr[i];
                }
                else if (iarr[i] <= storage[count])
                {
                    storage[++count] = iarr[i];
                }
                else
                {
                    int k, j, mid;
                    for (k = 0, j = iarr.Length; k != j - 1; )
                    {
                        mid = (k + j) / 2;
                        int OK = (storage[mid] >= iarr[i]) ? k = mid : j = mid;
                    }
                    storage[j] = iarr[i];
                }
            }
            return count + 1;
        }
        
    }
}
